In the field of wireless communication, the multi-input and multi-output (MIMO) system provides effective and promising solutions for achieving high data-rate with reliable transmission.
For example, in an MIMO communication system having M receiving antenna for receiving N transmitting signals from N transmitting antennas, for each transmitted vector, the received signals can be shown as below:
                                                        y              =                            ⁢                                                [                                                                                                              y                          1                                                                                                                                                              y                          2                                                                                                                                    ⋮                                                                                                                                      y                          M                                                                                                      ]                                =                                                                            [                                                                                                                                  h                                                              1                                ,                                1                                                                                                                                                                        h                                                              1                                ,                                2                                                                                                                                          …                                                                                                              h                                                              1                                ,                                N                                                                                                                                                                                                                        h                                                              2                                ,                                1                                                                                                                                                                        h                                                              2                                ,                                2                                                                                                                                          …                                                                                                              h                                                              2                                ,                                N                                                                                                                                                                                          ⋮                                                                                ⋮                                                                                ⋱                                                                                ⋮                                                                                                                                                              h                                                              M                                ,                                1                                                                                                                                                                        h                                                              M                                ,                                2                                                                                                                                          …                                                                                                              h                                                              M                                ,                                N                                                                                                                                                        ]                                        ⁡                                          [                                                                                                                                  x                              1                                                                                                                                                                                          x                              2                                                                                                                                                            ⋮                                                                                                                                                              x                              N                                                                                                                          ]                                                        +                                                                                                                      ⁢                                                [                                                                                                              n                          1                                                                                                                                                              n                          2                                                                                                                                    ⋮                                                                                                                                      n                          M                                                                                                      ]                                ⁢                                                                                                    M                        ≥                        N                                                                                                                                                                          h                                                      i                            ,                            j                                                                          ∼                                                  i                          .                          i                          .                          d                          .                                                      CN                            ⁡                                                          (                                                              0                                ,                                1                                                            )                                                                                                                                                                                                                                                        n                          i                                                ∼                                                  i                          .                          i                          .                          d                          .                                                      CN                            ⁡                                                          (                                                              0                                ,                                                                  σ                                  2                                                                                            )                                                                                                                                                                                                                                                  =                            ⁢                              Hx                +                n                                                                        Equation        ⁢                                  ⁢                  (          1          )                    Where y is the received vector having M elements, x is the vector representing the transmitted signals, H is the channel matrix of the MIMO communication system, and n is the noise vector. If there is no interfering source that continuously affects the communication system, in other words, the noises existing in the communication system randomly occur. Therefore, the relationship between y and x are dependent upon the channel matrix H and a disturbed term.
Please refer to FIG. 1, which schematics an algorism for sphere decoders known to the art at a 2N-dimensional space. According to FIG. 1, a white spot indicated as receiving point shows the location of a received signal (an element of the vector y) in the 2N-dimensional space having plural mesh points, each of which indicates the coordination of the transmitting points (signals). An arrow in FIG. 1 shows a radius of a 2N-dimensional hypersphere. The length of the arrow indicates a predetermined value. A number of calculations are performed by calculating for the distance between each of the mesh point inside the 2N-dimensional hypersphere and the receiving point to identify the mesh point having the smallest distance to the receiving point.
An IEEE paper, “A Novel Approach for K-best MIMO Detection and its VLSI Implementation”, provides a method of searching for candidate nodes. The searching method set forth above can be split into N layers of searching for candidates on complex planes. Please refer to FIG. 2, which schematics the method of searching for candidates known to the art. The method is doing search from a center of searching and starting from a search inside the area of a circle centered at the center of searching and having a radius of an initial value. If an effective transmitting (signal) point is found, the initial value of the radius is considered as the path value of the founded effective transmitting (signal) point. Then the radius is increased step by step until the circle encompasses all the effective transmitting (signal) points on the complex plane. During the process, the value of the radius when the circle touches an effective transmitting (signal) point is considered as the path value of the effective transmitting (signal) point. However, this method has some large defects: (1) For a particular circle, the amount of sampling points shall be sufficiently large so as to effectively contact all the nodes on the circle. For a particular value of the radius, each of the sampled points on the circle needs to be checked for the path value thereof. Therefore, the total amount of calculation is huge. (2) The calculated path values are not the exact values, particularly when the radius is gradually enlarged. (3) If there are a large number of effective transmitting (signal) points to be sampled, either repeated sampling or missing sampling might occur. So, the author of the paper adds a sub-module of redundancy remover to avoid such a dilemma.
Two searching algorithms, namely Schnorr-Eucher (SE) enumeration and the K-best method, are widely adopted particularly in the use of sphere decoders. However, the current methods for searching for the optimum transmitting points on a complex plane cannot be both economical and reliable. The SE enumeration can achieve the same performance as the maximum-likelihood (ML) detector, which searches all possible combinations of transmitted symbols, with reduced complexity. To overcome the abovementioned issues, the K-best method was introduced. The K-best method is proposed to avoid the mentioned issues by choosing an integer number k as the number of survival candidate nodes to be calculated for next layer of a searching tree, when the process of searching for the optimum transmitting points is simulated with the searching tree model. However, the K-best method is a trade-off between the performance and the computation loading, when determining the value of k.
Whenever the number k is determined, only the k candidate nodes in each layer of the searching tree will be reserved for later calculation while the other candidate nodes will be given up. If the number k is small, the K-best method would save a large amount of calculations. But the problem is: there is a good chance to give up the optimum candidates at the early stage of the calculation.